package com.example.hashtable;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 *
 *  示例 1：
 * 输入：nums = [1,2,0]
 * 输出：3
 *
 *  示例 2：
 * 输入：nums = [3,4,-1,1]
 * 输出：2
 *
 *  示例 3：
 * 输入：nums = [7,8,9,11,12]
 * 输出：1
 */
public class Leetcode41_FirstMissingPositive {
    public static void main(String[] args) {

        int[] nums = {3, 4, -1, 1};
        nums = new int[] {1, 2, 0};
//        nums = new int[] {7, 8, 9, 11, 12};
//        nums = new int[] {1, 2, 5};
//        nums = new int[] {1, 100};
//        nums = new int[] {-1, -2, -60, 40, 43};

        System.out.println(new Solution().firstMissingPositive(nums));
    }

    static class Solution {

        /**
         * 对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。
         * 这是因为如果 [1,N] 都出现了，那么答案是 N+1，否则答案是 [1,N] 中没有出现的最小正整数
         *
         * @param nums
         * @return
         */
        public int firstMissingPositive2(int[] nums) {
            int len = nums.length;
            // 将所有小于0的元素变为 len + 1
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= 0) nums[i] = len + 1;
            }

            // 将所有小于等于 len 的变为负数
            for (int i = 0; i < len; ++i) {
                int num = Math.abs(nums[i]);
                if (num <= len) {
                    nums[num - 1] = -Math.abs(nums[num - 1]);
                }
            }
            // 返回第一个大于0的元素的下一个下标
            for (int i = 0; i < len; ++i) {
                if (nums[i] > 0) {
                    return i + 1;
                }
            }

            return len + 1;
        }

        /**
         * 暴力法
         * @param nums
         * @return
         */
        public int firstMissingPositive1(int[] nums) {
            Arrays.sort(nums);
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                map.put(nums[i], i);
            }

            // 最大值都比0小
            if (nums[nums.length - 1] <= 0) return 1;

            if (nums[0] > 1) {
                return 1;
            }  else {
                if (!map.containsKey(1)) {
                    return 1;
                }

                for (int i = 0; i < nums.length; i++) {
                    int tmp = nums[i] - 1;
                    int tmp2 = nums[i] + 1;

                    if (tmp > 0 && !map.containsKey(tmp)) return tmp;

                    if (tmp2 > 0 && !map.containsKey(tmp2)) return tmp2;
                }
            }

            return nums[nums.length - 1] + 1;
        }

        public int firstMissingPositive(int[] nums) {
            return firstMissingPositive2(nums);
        }
    }
}
